package com.xiayuanxing.arithmetic.DataStructures.HashTable;

/**
 * @program: arithmetic
 * @description: 哈希表
 * @author: xia yuan xing
 * @create: 2021-10-05 14:55
 */
public class HashTableDemo {
    public static void main(String[] args) {

    }
}


/**
 * 哈希表
 */
class HashTable {

    private EmpLinkedList[] empLinkedListArray;
    //表示有多少条链表
    private int size;

    //构造器
    public HashTable(int size) {
        this.size = size;
        //初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];

        //初始化哈希表里的链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }

    }

    /**
     * 添加雇员
     *
     * @param emp
     */
    public void add(Emp emp) {
        //根据员工的id，得到员工应该添加到哪条链表
        int number = hashFun(emp.id);
        //将雇员添加到对应的链表中
        empLinkedListArray[number].add(emp);
    }

    /**
     * 遍历所有的链表（遍历哈希表）
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }


    public void findEmpById(int id){
        //根据员工的id，得到员工应该添加到哪条链表
        int number = hashFun(id);
        //将雇员添加到对应的链表中
        Emp emp = empLinkedListArray[number].findEmpById(id);
        if (emp == null){
            System.out.println("没有找到该雇员");
        }else {
            System.out.println("该雇员信息为："+emp.toString());
        }

    }

    /**
     * 编写散列函数，使用简单取模法
     */
    public int hashFun(int id) {
        return id % size;
    }
}


/**
 * 雇员
 */
class Emp {
    public int id;
    public String name;
    //next默认为null
    public Emp next;

    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}


/**
 * 创建EmpLinkedList,表示链表
 */
class EmpLinkedList {

    //头指针，执行第一个Emp,因此我们这个链表的head是直接指向第一个Emp
    //默认为null
    private Emp head;

    /**
     * 添加雇员到链表
     * 说明：
     * 1.假定添加雇员时，id是自增长的，即id的分配总是从小到大，所以直接将雇员添加到链表后面
     *
     * @param emp
     */
    public void add(Emp emp) {
        //如果是第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                //说明到了链表最后
                break;
            }
            //后移
            curEmp = curEmp.next;
        }
        //退出时，直接将雇员放在最后
        curEmp.next = emp;
    }


    /**
     * 遍历链表
     */
    public void list(int no) {

        //校验是否为空
        if (head == null) {
            System.out.println("第" + no + 1 + "条链表为空！");
            return;
        }

        System.out.println("第" + no + 1 + "条链表信息为：");
        //辅助指针
        Emp curEmp = head;

        while (true) {
            System.out.printf("=> id=%d name=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {
                //说明curEmp已经是最后的节点
                break;
            }
            //后移
            curEmp = curEmp.next;
        }
        System.out.println();
    }


    /**
     * 根据id查找雇员
     *
     * @param id
     * @return
     */
    public Emp findEmpById(int id) {

        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空!");
            return null;
        }

        //创建辅助指针
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {
                //说明找到了
                break;
            }
            //退出
            if (curEmp.next == null) {
                //说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            //后移
            curEmp = curEmp.next;
        }
        return curEmp;
    }

}